
import math
import random

from pandas import DataFrame, read_excel
from matplotlib import pyplot as plt


def city_distance(city_coordinates):  # 计算城市间距离；输入：城市坐标；输出：城市间距离矩阵-dis_matrix
    distance_matrix = DataFrame(data=None, columns=range(len(city_coordinates)), index=range(len(city_coordinates)))
    for i in range(len(city_coordinates)):
        xi, yi = city_coordinates[i][0], city_coordinates[i][1]
        for j in range(len(city_coordinates)):
            xj, yj = city_coordinates[j][0], city_coordinates[j][1]
            distance_matrix.iloc[i, j] = round(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2), 2)
    return distance_matrix


def greedy(city_coordinates, distance_matrix):  # 贪婪策略构造初始解,初始化时将VRP简化为TSP进行构造。输入：节点坐标,距离矩阵输出：初始解
    distance_matrix = distance_matrix.astype('float64')
    for i in range(len(city_coordinates)):
        distance_matrix.loc[i, i] = math.pow(10, 10)
    distance_matrix.loc[:, 0] = math.pow(10, 10)  # 0不在编码内
    line = []  # 初始化
    now_city = random.randint(1, len(city_coordinates) - 1)  # 随机生成出发城市
    line.append(now_city)  # 添加当前城市到路径
    distance_matrix.loc[:, now_city] = math.pow(10, 10)  # 更新距离矩阵，已经过城市不再被取出
    for i in range(1, len(city_coordinates) - 1):
        next_city = distance_matrix.loc[now_city, :].idxmin()  # 距离最近的城市
        line.append(next_city)  # 添加进路径
        distance_matrix.loc[:, next_city] = math.pow(10, 10)  # 更新距离矩阵
        now_city = next_city  # 更新当前城市
    return line


def fitness(route, demands, distance_matrix, capacities, m_distance, start, cost):  # 贪婪策略分配车辆（解码），计算路径距离
    # 输入：路径，客户需求,城市间距离矩阵，车辆最大载重,车辆最大行驶距离,车辆启动成本,车辆单位距离行驶成本；输出：分车后路径,适应度
    route_car, fit = [], []  # 初始化
    for j in range(len(route)):
        bird = route[j]
        lines = []  # 存储线路分车
        line = [0]  # 每辆车服务客户点
        dis_sum = 0  # 线路距离
        dis, d = 0, 0  # 当前客户距离前一个客户的距离、当前客户需求量
        i = 0  # 指向配送中心
        while i < len(bird):
            if line == [0]:  # 车辆未分配客户点
                dis += distance_matrix.loc[0, bird[i]]  # 记录距离
                line.append(bird[i])  # 为客户点分车
                d += demands[bird[i]]  # 记录需求量
                i += 1  # 指向下一个客户点
            else:  # 已分配客户点则需判断车辆载重和行驶距离
                if (distance_matrix.loc[line[-1], bird[i]] + distance_matrix.loc[bird[i], 0] + dis <= m_distance) & (
                        d + demands[bird[i]] <= capacities):
                    dis += distance_matrix.loc[line[-1], bird[i]]
                    line.append(bird[i])
                    d += demands[bird[i]]
                    i += 1
                else:
                    dis += distance_matrix.loc[line[-1], 0]  # 当前车辆装满
                    line.append(0)
                    dis_sum += dis
                    lines.append(line)  # 下一辆车
                    dis, d = 0, 0
                    line = [0]
        dis += distance_matrix.loc[line[-1], 0]  # 最后一辆车
        line.append(0)
        dis_sum += dis
        lines.append(line)
        route_car.append(lines)
        fit.append(round(cost * dis_sum + start * len(lines), 1))
    return route_car, fit


def crossover(bird, p_line, g_line, weight, c_1, c_2):  # 采用顺序交叉方式；交叉的parent1为粒子本身，
    # 分别以w/(w+c1+c2),c1/(w+c1+c2),c2/(w+c1+c2)的概率接受粒子本身逆序、当前最优解、全局最优解作为parent2,只选择其中一个作为parent2；
    # 输入：粒子,当前最优解,全局最优解,惯性因子,自我认知因子,社会认知因子；输出：交叉后的粒子-croBird；
    croBird = [None] * len(bird)  # 初始化
    parent1 = bird  # 选择parent1
    randNum = random.uniform(0, sum([weight, c_1, c_2]))  # 选择parent2（轮盘赌操作）
    if randNum <= weight:
        parent2 = [bird[i] for i in range(len(bird) - 1, -1, -1)]  # bird的逆序
    elif randNum <= weight + c_1:
        parent2 = p_line
    else:
        parent2 = g_line
    start_pos = random.randint(0, len(parent1) - 1)  # parent1-> croBird
    end_pos = random.randint(0, len(parent1) - 1)
    if start_pos > end_pos:
        start_pos, end_pos = end_pos, start_pos
    croBird[start_pos:end_pos + 1] = parent1[start_pos:end_pos + 1].copy()
    list2 = list(range(0, start_pos))  # parent2 -> croBird
    list1 = list(range(end_pos + 1, len(parent2)))
    list_index = list1 + list2  # croBird从后往前填充
    j = -1
    for i in list_index:
        for j in range(j + 1, len(parent2) + 1):
            if parent2[j] not in croBird:
                croBird[i] = parent2[j]
                break
    return croBird


def draw(car_routes, city_coordinates, x_, y_):  # 画路径图,迭代图;输入：路径，城市坐标；输出：路径图，迭代图
    color = ['green', 'gray', 'blue', 'red', 'orange'] * 10
    for i, route in enumerate(car_routes):
        x, y = [], []
        for j in route:
            Coordinate = city_coordinates[j]
            x.append(Coordinate[0])
            y.append(Coordinate[1])
        x.append(x[0])
        y.append(y[0])
        plt.plot(x, y, 'o-', color=color[i], alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()
    plt.plot(x_, y_)
    plt.xlabel('iter times')
    plt.ylabel('value')
    plt.show()


if __name__ == '__main__':
    points, demand = [], []
    df = read_excel('cvrp.xls')  # 读入数据,
    for i_ in range(df.shape[0]):
        points.append([df['x'][i_], df['y'][i_]])
        demand.append(df['需求量'][i_])
    capacity = df['车辆参数'][0]  # 车辆最大容量
    distabce = df['车辆参数'][1]  # 车辆最大行驶距离
    C0 = df['车辆参数'][2]  # 车辆启动成本
    C1 = df['车辆参数'][3]  # 车辆单位距离行驶成本
    birdNum = int(df['算法参数'][0])  # 粒子数量
    w = df['算法参数'][1]  # 惯性因子
    c1 = df['算法参数'][2]  # 自我认知因子
    c2 = df['算法参数'][3]  # 社会认知因子
    iterMax = int(df['其它参数'][0])  # 迭代次数
    iterI = 1  # 当前迭代次数
    bestfit = []  # 记录每代最优值

    dis_matrix = city_distance(points)  # 计算城市间距离
    birdPop = [greedy(points, dis_matrix) for i in range(birdNum)]  # 贪婪算法构造初始解
    birdPop_car, fits = fitness(birdPop, demand, dis_matrix, capacity, distabce, C0, C1)  # 分配车辆，计算种群适应度
    gBest = pBest = min(fits)  # 全局最优值、当前最优值（自我认知部分）
    gLine = pLine = birdPop[fits.index(min(fits))]  # 全局最优解、当前最优解（社会认知部分）
    gLine_car = pLine_car = birdPop_car[fits.index(min(fits))]
    bestfit.append(gBest)
    iter_x, iter_y = [], []
    while iterI <= iterMax:  # 迭代开始
        for i_ in range(birdNum):
            birdPop[i_] = crossover(birdPop[i_], pLine, gLine, w, c1, c2)
        birdPop_car, fits = fitness(birdPop, demand, dis_matrix, capacity, distabce, C0, C1)  # 分配车辆，计算种群适应度
        pBest, pLine, pLine_car = min(fits), birdPop[fits.index(min(fits))], birdPop_car[fits.index(min(fits))]
        if min(fits) <= gBest:
            gBest, gLine, gLine_car = min(fits), birdPop[fits.index(min(fits))], birdPop_car[fits.index(min(fits))]
        bestfit.append(gBest)
        iter_x.append(iterI)  # 打印当前代数和最佳适应度值
        iter_y.append(gBest)
        print(f'迭代次数：{iterI}/{iterMax} 最优解：{gBest}')
        iterI += 1  # 迭代计数加一
    print(f'迭代{iterI-1}次 最优解：{gBest} 当前最优路线：👇')  # 路径顺序
    for i_ in range(len(gLine_car)):
        print(f'车辆{i_ + 1} 路径 {"->".join([str(j) for j in gLine_car[i_]])}')
    draw(gLine_car, points, iter_x, iter_y)  # 画路径图
    